#include <stdio.h>

int setWay(int map[][7], int i, int j);
int setWay2(int map[][7], int i, int j);
void show(int map[][7]);
int count = 0;

int main(void)
{
	//先创建一个数组，模拟迷宫
	//地图
	int map[8][7];

	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 7; j++)
			map[i][j] = 0;
	//使用1表示墙

	//上下全部置为1
	for (int i = 0; i < 7; i++)
	{
		map[0][i] = 1;
		map[7][i] = 1;
	}

	//左右全部置为1
	for (int i = 0; i < 8; i++)
	{
		map[i][0] = 1;
		map[i][6] = 1;
	}

	//设置挡板，用1表示
	map[3][1] = 1;
	map[3][2] = 1;
	map[4][2] = 1;
	map[4][3] = 1;
	map[4][4] = 1;
	map[3][4] = 1;

	// map[1][2] = 1;
	// map[2][2] = 1;

	//输出地图
	printf("地图的情况:\n");
	show(map);

	int ret = setWay2(map, 1, 1);

	if (ret == 0)
		printf("未找到路径\n");
	//输出新的地图，小球走过，并标识过的地图
	printf("小球走过的地图的情况:\n");
	show(map);
	printf("count = %d\n", count);

	return 0;
}

//使用递归回溯来给小球找路
//说明
// 1. map表示地图
// 2. i,j表示从地图的哪个位置开始出发
// 3. 如果找到通路，就返回true，否则返回false
// 4. 约定：当map[i][j]为0时表示该点没有走过 当为1表示墙；2表示通路可以走；3表示该点已经走过，但是走不通
// 5. 在走迷宫时，需要确定一个策略：下-->右-->上-->左
//策略：上-->右-->下-->左
int setWay2(int map[][7], int i, int j)
{
	if (map[6][5] == 2) //道路已经找到ok
		return 1;
	else
	{
		if (map[i][j] == 0) //如果当前这个点还没有走过
		{
			//按照策略走
			map[i][j] = 2;		   //假定该点是可以走通
			++count;
			if (setWay2(map, i - 1, j)) //向上走
				return 1;
			else if (setWay2(map, i, j + 1)) //向右走
				return 1;
			else if (setWay2(map, i + 1, j)) //向下走
				return 1;
			else if (setWay2(map, i, j - 1)) //向左走
				return 1;
			else               //说明该点走不通，是死路
			{
				map[i][j] = 3;
				--count;
				return 0;
			}
		}
		else //如果map[i][j] != 0,可以是1(墙，走不了)，2(通路，已经走过了)，3(死路)
			return 0;
	}
}

//策略：下-->右-->上-->左
int setWay(int map[][7], int i, int j)
{
	if (map[6][5] == 2) //道路已经找到ok
		return 1;
	else
	{
		if (map[i][j] == 0) //如果当前这个点还没有走过
		{
			//按照策略走
			map[i][j] = 2;		   //假定该点是可以走通
			if (setWay(map, i + 1, j)) //向下走
				return 1;
			else if (setWay(map, i, j + 1)) //向右走
				return 1;
			else if (setWay(map, i - 1, j)) //向上走
				return 1;
			else if (setWay(map, i, j - 1)) //向左走
				return 1;
			else //说明该点走不通，是死路
			{
				map[i][j] = 3;
				return 0;
			}
		}
		else //如果map[i][j] != 0,可以是1(墙，走不了)，2(通路，已经走过了)，3(死路)
			return 0;
	}
}

void show(int map[][7])
{
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 7; j++)
			printf("%d  ", map[i][j]);
		putchar('\n');
	}
}